FIELD OF THE INVENTION
The present invention relates to a transform processing circuit which is particularly, but not exclusively, advantageous for performing Fourier Transforms.
The Fourier Transform is an algorithm which has many applications in signal processing techniques and is used to transform variables, functions and data from a first domain to a second domain and the inverse of the algorithm performs the reverse transformation. The discrete version of the Fourier Transform is given by the following equation where x(k), k=0,1,2 . . . N-1, represents complex sample points in a first domain, N is the number of sample points, and X(n), n=0 . . . N-1, represents the transformed points in a second domain. ##EQU1## The inverse transform is as follows. ##EQU2##
For the purposes of simplifying the remaining description the first domain is chosen to be the time domain and the second domain is chosen to be the frequency domain.
The FFT was introduced in 1965 and reduces the number of arithmetic operations which need to be performed in order to carry out an N point transform. The FFT now forms the basis of efficient algorithms for filtering, convolution, correlation, smoothing and other signal processing techniques. The transform is also used in the operation of signal processors such as those employed in spectrum analysers and sonar array beam formers.
A number of FFT processors have been proposed which receive N sample points and produce N transformed points, corresponding to the samples, in a "bit reversed order". Bit, reversed order means the transformed points are not produced in the same order as the sample points are received, e.g. for N=4, x(0), x(1), x(2), x(3) are received and X(0), X(2), X(1) and X(3) are produced, respectively.
Once a number of points have been transformed it is often desirable to multiply the transformed points by a predetermined frequency response and then inverse transform the result into a number of output points in the time domain, using the inverse FFT. This enables the effect of the response on real time signals to be determined and allows a precise frequency response to be applied to a real time signal. To do this, however, a separate processing unit is normally required to perform the inverse FFT (IFFT) and the bit reversed order of the transformed points must be corrected before the points are applied to the frequency response. The points produced after application of the response are transformed by the IFFT processing unit, and the transformed points generated thereby are in the time domain and represent the real time effect of the response. The transformed points in the time domain, however, are produced in bit reversed order and again an adjusting process needs to be performed so as to produce a natural order representation of a real time signal. Alternatively in performing the above procedure the frequency response may be bit reversed, applied to the bit reversed output of the FFT processor and the result reordered before being applied to an IFFT processing unit, yet the end result will still appear in bit reversed order.
The bit reversal problem also occurs in performing transforms other than the FFT and it is desirable to provide a general transform processing circuit which is able to overcome this problem.
A further problem associated with known FFT processors, apart from the bit reversal problems discussed above, is that the range of applications for FFT processors is limited by their speed of operation. To enhance the speed of operation it is desirable to perform as many operations as possible in parallel when performing an N point transform, for example, by using a pipelining technique. Known FFT processors are also usually configured by controlling the steps of a transform using software and, hence, it is also desirable, in order to obtain improvements in speed and size, to provide an FFT processor which may be configured in hardware to perform a predetermined FFT algorithm.